The present invention relates generally to processing computer data and, more particularly, to mapping physical addresses in a virtual address system.
One of the elements within a typical computer system is a memory management unit (MMU). The MMU includes hardware and software that work in conjunction with a processing unit (i.e. CPU) of the computer system when data is retrieved from memory. In order to allow more effective retrieval of data such as image data from memory, it is conventional for the processing unit to employ xe2x80x9cvirtualxe2x80x9d addresses which in turn correspond to physical addresses in physical memory, as part of a virtual address system.
When accessing data, the processing unit generates virtual addresses to access physical memory. Before these virtual addresses can be used to access data in physical memory, they must be translated into physical addresses. It is the MMU that controls the allocation and use of physical memory and provides the processing unit with mapping information which enables access to the data in the physical memory.
Prior Art FIG. 2A illustrates one example of mapping virtual addresses 100 to segments of physical memory 102 commonly referred to as xe2x80x9cpagesxe2x80x9d 104. A page 104 is a block of memory typically having a predetermined size. The specific size of a page 104 varies from system to system. A common page size is 4096 bytes.
The MMU maintains tables of mapping information, or xe2x80x9cpage tablesxe2x80x9d, that keep track of where each page of virtual memory is located in physical memory. The processing unit uses this mapping information when it translates virtual addresses to physical addresses. To this end, the mapping of virtual addresses through page tables in a virtual address system provides a large virtual address space, and allows programs to run on hardware with smaller physical memory configurations.
An example of a page table is shown in Prior Art FIG. 2B. The page table 200 of Prior Art FIG. 2B contains Page Table Entries (PTEs) 202, each one of which defines a mapping between a single virtual page and a physical page of memory by providing a physical address 204 of the physical page of memory. In addition to containing the physical address, the page table 200 may also include a plurality of flags 206 as a component of each PTE 202. Examples of such flags 206 may include a lock, read, write, and/or page present flag.
Thus a given virtual page of memory is xe2x80x9cmappedxe2x80x9d to a page of physical memory by a specific PTE. The PTE is thus capable of xe2x80x9cmappingxe2x80x9d the virtual page to a physical page of memory.
The processing unit must frequently access the contents of a PTE as a consequence of managing virtual addresses and physical memory. In particular, the processing unit must access a PTE every time a virtual address must be mapped to a specific given physical page of memory. In the case of processing graphics data, and more particularly 3-D graphics data, such constant accessing of the page table becomes especially burdensome on the processing unit, taking a significant portion of the unit""s computational cycles.
There is therefore a need for a system that allows for more efficient mapping of physical memory in a virtual address system by minimizing a number of look-ups in a PTE data structure during the mapping process.
A method, apparatus and article of manufacture are provided for minimizing the number of look-ups in a page table entry (PTE) data structure during mapping of physical memory. First, a primary virtual address in a PTE data structure is accessed. Next, it is determined whether a primary physical address corresponding to the accessed primary virtual address in the PTE data structure is associated with a physical page having at least one contiguous physical page.
Such determination may be facilitated by using headers for each of the entries in the PTE data structure. These headers may be read upon accessing the primary physical address in the PTE data structure in order identify whether any contiguous physical pages exist and, if so, how many and where they are located.
If it is determined that at least one contiguous physical page exists, information relating to both the primary virtual address, primary physical address, and any contiguous physical pages in the PTE data structure is retrieved in a single look-up. It can thus be appreciated that a look-up process in a PTE data structure having physical pages with a significant amount of contiguity will be accelerated in a very desirable manner. Such acceleration is a direct result of fewer required look-ups in the PTE data structure and more information being retrieved during each look-up.
If it is determined that the primary physical address is not associated with any contiguous physical pages, normal operation is carried out and information is only retrieved relating to the primary physical address in the PTE data structure.
In the case where the primary physical address is not associated with any contiguous pages, the information that is retrieved may include bits representative of the primary physical address. If, however, at least two contiguous pages are identified, the retrieved information may include information for allowing the calculation of bits representative of the contiguous physical addresses and the corresponding range of the virtual addresses. For example, the retrieved information may include a minimum and maximum limit of the virtual or physical address range.
These and other advantages of the present invention will become apparent upon reading the following detailed description and studying the various figures of the drawings.